Application programs for complex interrelated data and high performance requirements, such as computer aided design (CAD) and computer aided software engineering (CASE), frequently use a collection of "objects" to represent data of interest. Such applications attach various "attributes" to these objects in order to record the characteristics (or "attribute values") of the objects. The mechanism used to maintain the attributes of a data model seeks to satisfy the following requirements: (1) an attribute value for a particular object must be quickly accessible; (2) storage requirements to maintain the attributes should be minimized; and (3) the application must be able to dynamically add and remove "attribute values". (In any object-oriented data model, "attribute values" must be changeable.)
A first classical mechanism used by many commercially available data models is to maintain attribute values in "parallel tables" (see FIG. 1). In a parallel tables configuration, each object of a "category" is assigned a unique integer index (1,2, . . . N) and "attribute values" are held in a memory array comprised of equal length attribute tables (e.g., Attribute 1 Values table, Attribute 2 Values table, etc.) The array element at an object's index comprises the attribute value for that object. Thus, each attribute is assigned its own table within the data model. Accessing an attribute value involves simply indexing into the appropriate array using the object's index (1,2, . . . N). The array holds just attribute values, with no extra storage costs for linked lists, hash tables, etc. Whenever a new attribute is to be added or removed, the array which holds the attribute values must be allocated or deallocated, so the requirement for dynamism is satisfied. A significant problem with this approach, however, is that space is allocated for all objects, even if they might not need the attribute.
This problem with the parallel tables approach arises from the scope of uniqueness of object indices. Generally, objects used via application programs are "categorized". For example, in an electronic design automation program, categories such as Block, Net, and Pin are frequency used. Generally, a particular type of attribute applies to only one or a few categories. By way of example, "Pin elevation" is an attribute of Pins, and "Block function" is an attribute of Blocks. If every object is given a unique index, then space in the Block function table must be allocated for every Pin object, even though Pins do not have any Block function to be recorded. Obviously, this can comprise a significant waste of memory space.
A simple solution to the problem might be to limit the scope or uniqueness of the object indices to a category. Thus, no two Block objects would have the same index, but a Block and a Pin might have the same index. No relationship would be implied by objects in different categories having the same indices; the indices in different categories would be completely independent. As indices would be bound to categories, so would attributes be bound to categories. Each attribute would be associated with a category and be maintained in a table (array) which would be indexed by the object indices of that category. By way of example, see FIG. 2 wherein category A objects have associated attribute 1 & 2 values, category B objects have associated attribute 3 & 4 values, and category C objects have associated attribute 5 & 6 values.
Unfortunately, the situation is further complicated when hierarchical relationships are established between "categories". In particular, some applications require only a very course categorization of "objects" for example dividing objects into just Blocks, Nets, and Pins. In such applications, there may be a need to access attributes associated with the general categories. In contrast, other applications may require a much finer categorization of objects. For example, there may be TIBBlocks, CMOSBlocks, MacroBlocks, ChipBlocks, etc. Unique attribute information may need to be associated with each of these object categories.
In order to support the various granularities of categorization required by different applications, object-oriented models permit categories to be organized hierarchically (see FIG. 3). Each "category" may be related to another category as its "supercategory." Even though an object belongs to one particular category, an application which prefers a relatively course granularity structure can treat the "object" as if it were a member of that category's "supercategory", or even that "supercategory's" "supercategory", etc.
The processing mechanism disclosed herein provides an efficient technique for locating one of multiple parallel tables maintained separate from but in association with categories of an object-oriented data model so that attribute values for objects within the categories can be accessed, while minimizing waste of memory space.